package com.rong.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 冒泡排序，时间复杂度o(n^2)
 * 
 * 思路：经过一轮排序之后，最大(或者最小)的再右边
 * 
 * @author liurong
 *
 */
public class BubbleSort {

	public static void main(String[] args) {
//		int[] sourceArr = new int[] { 1, 5, 12, 24, 35, 66, 100 };
		int[] sourceArr = new int[] { 12, 24, 5, 35, 1, 66, 100 };
		sort(sourceArr);
		System.out.println(Arrays.toString(sourceArr));

		sourceArr = new int[100000];
		for (int i = 0; i < 100000; i++) {
			sourceArr[i] = new Random().nextInt(100000);
		}

		long start = System.currentTimeMillis();
		sort(sourceArr);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

	public static void sort(int[] arr) {
		int length = arr.length;
		int temp = 0;
		boolean flag = false;
		for (int i = 0; i < length; i++) {
			for (int j = 1; j < length - i; j++) {
				if (arr[j] < arr[j - 1]) {
					temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
					flag = true;
				}
			}
			if (!flag) {
				break;
			} else {
				flag = false;
			}
		}
	}
}
